package leedcode_path.回溯;

import java.util.ArrayList;
import java.util.List;
import java.util.ResourceBundle;

public class 组合 {
    /*
    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
    递归三部曲：参数，终止条件，遍历过程
示例 1：
输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]*/
    List<Integer> path = new ArrayList<Integer>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return res;
    }
    public void backtracking(int n,int k,int startindex){
        if (path.size()==k){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startindex; i <=n-(k-path.size())+1 ; i++) {
            path.add(i);
            backtracking(n,k,i+1);
            path.remove(path.size()-1);
        }

    }
}
